#pragma once

#include <iostream>
#include <vector>

using namespace std;

void quick_sort(std::vector<int>& nums, int left, int right)
{
	if (left >= right) return;

	int i = left, l = left - 1, r = right + 1, key = nums[left + right >> 1];
	while (i < r)
	{
		if (nums[i] < key) swap(nums[++l], nums[i++]);
		else if (nums[i] == key) i++;
		else swap(nums[--r], nums[i]);
	}
	quick_sort(nums, left, l), quick_sort(nums, r, right);
}
